#include <malloc.h>

typedef struct {
	int stack_value;
	int stack_value_heap_nono;
	int heap_value;
	int heap_value_stack_index;
} node_t;

typedef struct {
	unsigned node_nums;
	unsigned cap_node_nums;
	node_t* node_b;
} MinStack;

MinStack* minStackCreate() {
	MinStack* stack_heap_p = malloc(sizeof(MinStack));
	stack_heap_p->node_nums = 0;
	stack_heap_p->cap_node_nums = 1;
	stack_heap_p->node_b = malloc(sizeof(node_t));
	return stack_heap_p;
}

static node_t* _get_addr(node_t node_b[], int nono) {
	return &(node_b[nono - 1]);
}

static int _up(MinStack* min_stack_p, int origin_heap_nono, int value,
	       int stack_index) {
	node_t* node_b = min_stack_p->node_b;
	int nono = origin_heap_nono;
	node_t* node_p = _get_addr(node_b, origin_heap_nono);
	int node_value_stack_index = stack_index;
	while (nono >= 2) {
		int up_nono = nono >> 1;
		node_t* up_node_p = _get_addr(node_b, up_nono);
		int up_node_value = up_node_p->heap_value;
		if (up_node_value <= value) {
			break;
		}
		int up_node_value_stack_index =
			up_node_p->heap_value_stack_index;
		node_p->heap_value = up_node_value;
		node_p->heap_value_stack_index = up_node_value_stack_index;
		node_b[up_node_value_stack_index].stack_value_heap_nono = nono;
		nono = up_nono;
		node_p = up_node_p;
	}
	node_p->heap_value = value;
	node_p->heap_value_stack_index = node_value_stack_index;
	node_b[stack_index].stack_value_heap_nono = nono;
	return nono;
}

static int _down(MinStack* min_stack_p, int origin_heap_nono, int value,
		 int stack_index, int node_nums) {
	node_t* node_b = min_stack_p->node_b;
	int nono = origin_heap_nono;
	node_t* node_p = _get_addr(node_b, origin_heap_nono);
	while (1) {
		int left_nono = nono << 1;
		if (left_nono > node_nums) {
			break;
		}
		node_t* left_node_p = _get_addr(node_b, left_nono);
		int left_value = left_node_p->heap_value;
		int min_child_value = left_value;
		int min_child_nono = left_nono;
		node_t* min_child_p = left_node_p;
		int right_nono = left_nono + 1;
		if (right_nono <= node_nums) {
			node_t* right_node_p = _get_addr(node_b, right_nono);
			int right_value = right_node_p->heap_value;
			if (right_value < left_value) {
				min_child_value = right_value;
				min_child_nono = right_nono;
				min_child_p = right_node_p;
			}
		}
		if (value <= min_child_value) {
			break;
		}
		node_p->heap_value = min_child_value;
		int min_child_stack_index = min_child_p->heap_value_stack_index;
		node_p->heap_value_stack_index = min_child_stack_index;
		node_b[min_child_stack_index].stack_value_heap_nono = nono;
		node_p = min_child_p;
		nono = min_child_nono;
	}
	node_p->heap_value = value;
	node_p->heap_value_stack_index = stack_index;
	node_b[stack_index].stack_value_heap_nono = nono;
	return nono;
}

void minStackPush(MinStack* min_stack_p, int value) {
	node_t* node_b = min_stack_p->node_b;
	int old_nums = min_stack_p->node_nums;
	int new_nums = old_nums + 1;
	min_stack_p->node_nums = new_nums;

	int cap_node_nums = min_stack_p->cap_node_nums;
	if (new_nums > cap_node_nums) {
		int new_cap_node_nums = cap_node_nums << 1;
		if ((new_cap_node_nums >> 1) != cap_node_nums) {
			free(node_b);
			free(min_stack_p);
			return;
		}
		node_b = realloc(node_b, sizeof(node_t[new_cap_node_nums]));
		min_stack_p->node_b = node_b;
		min_stack_p->cap_node_nums = new_cap_node_nums;
	}

	node_t* new_tail_node_p = &(node_b[old_nums]);
	new_tail_node_p->stack_value = value;
	_up(min_stack_p, new_nums, value, old_nums);
}

void minStackPop(MinStack* min_stack_p) {
	node_t* node_b = min_stack_p->node_b;
	int old_nums = min_stack_p->node_nums;
	int new_nums = old_nums - 1;
	min_stack_p->node_nums = new_nums;

	node_t* old_tail_node_p = &(node_b[new_nums]);
	int pop_heap_nono = old_tail_node_p->stack_value_heap_nono;
	if (pop_heap_nono == old_nums) {
		return;
	}

	int heap_tail_value = old_tail_node_p->heap_value;
	int heap_tail_stack_index = old_tail_node_p->heap_value_stack_index;
	int nono_after_up = _up(min_stack_p, pop_heap_nono, heap_tail_value,
				heap_tail_stack_index);
	if (nono_after_up == pop_heap_nono) {
		_down(min_stack_p, pop_heap_nono, heap_tail_value,
		      heap_tail_stack_index, new_nums);
	}
}

int minStackTop(MinStack* min_stack_p) {
	node_t* node_b = min_stack_p->node_b;
	int nums = min_stack_p->node_nums;
	return node_b[nums - 1].stack_value;
}

int minStackGetMin(MinStack* min_stack_p) {
	return min_stack_p->node_b[0].heap_value;
}

void minStackFree(MinStack* min_stack_p) {
	free(min_stack_p->node_b);
	free(min_stack_p);
}
